题目传送门:http://pan.baidu.com/s/1qYPBdpU
数据生成器:http://paste.ubuntu.com/19351549/
OJ传送门:http://oi.cdshishi.net:8080/Problem/1719
这道题目,一看,SA的板题嘛!于是很高兴的码了SA
码完之后一对拍,发现,好像常数很大的样子,然而一看数据范围,嗯,一定是O(nlogn)的复杂度
结果,又被卡常了QAQ
说一说SA的做法:
首先在SA上二分,搞出len
然后再次在SA上二分,搞出最小的标号
然后总体复杂度O(6*n*log(n)),于是T了一个点QAQ
再来说一说SAM的做法(QJC说:这不是SAM的一眼题吗QAQ)
两个字串的lcp,是fail树上的lca,于是考虑在lca上染色的话,O(n)即可
另外,此题不是要求的不是后缀关系,是前缀关系,于是我们倒着建即可
SA版本:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 1000000+9; const int SGZ = 26; const int INF = 100000000; char pat[MAXN]; int n; namespace Suffix_Array{ #define SA Suffix_Array int height[MAXN],sa[MAXN],t1[MAXN],t2[MAXN],bot[MAXN]; int *tmp,*rank,m,K[MAXN],LEN[MAXN]; inline void ST_Advance(){ for (int i=1,k,len;i<=n;i++) { k = 0, len = 1; while (len < i) len *= 2, k++; K[i] = k; LEN[i] = len; } } struct Sparse_Table{ int MN[MAXN][20]; inline void init(int *arr){ for (int i=1;i<=n;i++) MN[i][0] = arr[i]; for (int k=1,lim=2;k<=19;k++,lim=1<<k) for (int i=1;i<=n-lim+1;i++) MN[i][k] = min(MN[i][k-1], MN[i+(1<<(k-1))][k-1]); } inline int query(int a, int b){ if (a > b) swap(a, b); int sta=(b-a+2)/2,k=K[sta],len=LEN[sta]; return min(MN[a][k], MN[b-len+1][k]); } }ST_num,ST_hei; inline void GetHeight(){ for (int i=1;i<=n;i++) if (rank[i] > 1) { int sta = max(0, height[rank[i-1]]-1); int p1 = sta + i, p2 = sta + sa[rank[i]-1]; while (pat[p1++] == pat[p2++]) sta++; height[rank[i]] = sta; } } inline void build(){ tmp = t1, rank = t2; n = strlen(pat+1); m = SGZ; for (int i=1;i<=n;i++) bot[tmp[i]=pat[i]-'a'+1]++; for (int i=2;i<=m;i++) bot[i] += bot[i-1]; for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i; rank[sa[1]] = m = 1; for (int i=2;i<=n;i++) if (tmp[sa[i]] != tmp[sa[i-1]]) rank[sa[i]] = ++m; else rank[sa[i]] = m; for (int k=1;k<=n;k*=2) { int T = 0; for (int i=n-k+1;i<=n;i++) tmp[++T] = i; for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++T] = sa[i]-k; for (int i=1;i<=m;i++) bot[i] = 0; for (int i=1;i<=n;i++) bot[rank[i]]++; for (int i=2;i<=m;i++) bot[i] += bot[i-1]; for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i]; swap(tmp, rank); rank[sa[1]] = m = 1; for (int i=2;i<=n;i++) if (tmp[sa[i]] != tmp[sa[i-1]] || tmp[sa[i]+k] != tmp[sa[i-1]+k]) rank[sa[i]] = ++m; else rank[sa[i]] = m; if (m >= n) break; } GetHeight(); ST_Advance(); ST_num.init(sa); ST_hei.init(height); } inline void solve(){ for (int w=1,tag=0;w<n;tag=0) { int mid, l = 1, r = rank[w] - 1, len = 0, ans = 0; while (l <= r) { mid = (l + r) / 2; if (ST_num.query(rank[w]-mid,rank[w]-1) < w) r = mid-1, len = mid; else l = mid+1; } if (len) ans = ST_hei.query(rank[w]-len+1, rank[w]); l = 1; r = n - rank[w]; len = 0; while (l <= r) { int mid = (l + r) / 2; if (ST_num.query(rank[w]+1, rank[w]+mid) < w) r = mid-1, len = mid; else l = mid+1; } if (len) ans = max(ans, ST_hei.query(rank[w]+1, rank[w]+len)); if (ans) { printf("%d ",ans); tag = ans; l = 1; r = rank[w]; len = 0; ans = INF; while (l <= r) { mid = (l + r) / 2; if (ST_hei.query(rank[w], rank[w]-mid+1) >= tag) l = mid+1, len = mid; else r = mid-1; } if (len) ans = ST_num.query(rank[w]-len,rank[w]-1); l = 1; r = n-rank[w]; len = 0; while (l <= r) { mid = (l + r) / 2; if (ST_hei.query(rank[w]+1, rank[w] + mid) >= tag) l = mid+1, len = mid; else r = mid-1; } if (len) ans = min(ans, ST_num.query(rank[w]+1, rank[w]+len)); printf("%d ",ans-1); w += tag; } else { printf("%d %d ",-1,(int)pat[w]); w ++; } } } }; int main(){ freopen("encrypt.in","r",stdin); freopen("encrypt.out","w",stdout); scanf("%s",pat+1); SA::build(); SA::solve(); return 0; }
SAM版本:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 1000000+9; const int SGZ = 27; char pat[MAXN]; int n; namespace Suffix_Automaton{ #define SAM Suffix_Automaton int ch[MAXN][SGZ],fail[MAXN],tag[MAXN],W=1; int cnt,last,dep[MAXN],pos[MAXN]; inline void extend(int i, int c){ int w = last; dep[pos[i]=last=++cnt] = dep[w]+1; while (w && !ch[w]) ch[w] = last, w = fail[w]; if (!ch[w]) fail[last] = 1; else { int nw = ch[w]; if (dep[nw] == dep[w] + 1) fail[last] = nw; else { int nnw = ++cnt; dep[nnw] = dep[w] + 1; memcpy(ch[nnw],ch[nw],sizeof(ch[nw])); fail[nnw] = fail[nw]; fail[nw] = fail[last] = nnw; while (ch[w] == nw) ch[w] = nnw, w = fail[w]; } } } inline void sign(int w, int val) { while (w && !tag[w]) tag[w] = val, w = fail[w]; if (W == val) { if (w <= 1) printf("-1 %d ",(int)pat[val]), W++; else printf("%d %d ",dep[w],tag[w]-1), W += dep[w]; } } inline void build(char *s){ n = strlen(s+1); cnt = last = 1; for (int i=n;i;i--) extend(i, pat[i]-'a'+1); for (int i=1;i<=n;i++) sign(pos[i], i); } }; int main(){ scanf("%s",pat+1); SAM::build(pat); return 0; }
看看SA将近4k的代码
再看看SAM只有1.2k的代码
SA,你还要我怎么爱你QAQ
Thank you for your article post.Really looking forward to read more. Much obliged.
Hey, thanks for the blog.Really thank you! Keep writing.
Im obliged for the blog. Cool.
Very informative blog article.Much thanks again. Keep writing.
Im obliged for the blog post.Thanks Again. Much obliged.
This is one awesome post.
Im thankful for the post.Thanks Again. Awesome.
I really like and appreciate your article post.Really thank you! Will read on…
Thanks for sharing, this is a fantastic blog.Much thanks again.
Appreciate you sharing, great blog post.Thanks Again. Much obliged.
Very neat article.Thanks Again. Awesome.
wow, awesome blog post.Much thanks again. Will read on…
Thanks so much for the post.Much thanks again. Keep writing.
Appreciate you sharing, great article post.Thanks Again.
Thanks for sharing, this is a fantastic blog article.Really looking forward to read more. Fantastic.
I am so grateful for your blog post.Much thanks again. Want more.
With havin so much content and articles do you ever run into
any issues of plagorism or copyright violation? My website
has a lot of completely unique content I’ve either written myself or outsourced but
it looks like a lot of it is popping it up all over the
internet without my authorization. Do you know any
methods to help protect against content from being ripped off?
I’d really appreciate it.
Wow, great blog.Much thanks again.
Great, thanks for sharing this blog.Thanks Again. Will read on…
Really informative post.Really thank you!
Howdy! I’m at work browsing your blog from my new apple iphone!
Just wanted to say I love reading through
your blog and look forward to all your posts! Carry on the
superb work!
I’m not that much of a internet reader to be honest but
your blogs really nice, keep it up! I’ll go ahead and bookmark your website to come back later.
All the best
Enjoyed every bit of your blog article.Much thanks again. Really Great.
Thanks again for the blog article.Really looking forward to read more.
Thanks designed for sharing such a fastidious idea, piece of
writing is fastidious, thats why i have read it fully
Hey, thanks for the article. Keep writing.
It’s going to be end of mine day, except before ending I am reading this fantastic
piece of writing to improve my knowledge.
Really informative blog article.Really thank you! Great.
Very good post.Thanks Again. Keep writing.
Hi there would you mind letting me know which web host you’re utilizing?
I’ve loaded your blog in 3 different web browsers and I must say this blog loads a lot faster then most.
Can you suggest a good internet hosting provider at a reasonable price?
Kudos, I appreciate it!
I really like and appreciate your blog article.Really thank you! Awesome.
I appreciate you sharing this article.Really thank you! Fantastic.
I’m not sure where you are getting your information, but great topic.
I needs to spend some time learning much more or
understanding more. Thanks for great info I was looking for this info for my mission.
Thanks so much for the blog.Really thank you! Really Cool.
Thanks for the blog post.Thanks Again. Much obliged.
Thanks for finally talking about >【NOI五连测】[D3T2] 加密 – Qizy’s Database <Liked it!
Looking forward to reading more. Great post.Really looking forward to read more. Awesome.
Thanks again for the article.Thanks Again. Awesome.
I want to to thank you for this excellent read!! I definitely enjoyed every bit of it.
I have got you bookmarked to check out new stuff
you post…
A round of applause for your article post.Really thank you! Cool.
I am so grateful for your article. Really Cool.
Im thankful for the article post.Thanks Again. Really Cool.
I think this is a real great article post.Much thanks again. Great.
Pretty! This was an extremely wonderful article. Thanks for providing these details.
Really appreciate you sharing this article post.Thanks Again. Awesome.
Great post! We are linking to this great article on our site.
Keep up the great writing.
Greetings from Ohio! I’m bored at work so I decided to
browse your website on my iphone during lunch break.
I enjoy the information you provide here and can’t wait to take a look when I get home.
I’m shocked at how fast your blog loaded on my phone ..
I’m not even using WIFI, just 3G .. Anyways,
wonderful site!
I want to to thank you for this great read!! I definitely loved every bit of it.
I have you book-marked to check out new stuff you post…
This is a topic that is close to my heart… Many thanks!
Exactly where are your contact details though?
Thanks for the blog.Much thanks again.
Its like you read my thoughts! You appear to know a lot approximately this, like you wrote the e
book in it or something. I think that you simply can do with some p.c.
to force the message house a bit, but instead of that, this is excellent
blog. A fantastic read. I’ll certainly be back.
Very informative article post.Really thank you! Awesome.
Really appreciate you sharing this article post.Really looking forward to read more. Keep writing.
I like what you guys are up too. Such clever work and reporting! Keep up the excellent works guys I¦ve incorporated you guys to my blogroll. I think it’ll improve the value of my web site 🙂
Very informative post.Much thanks again. Great.
Very informative blog.Really looking forward to read more. Will read on…
Thank you for your article post.Really thank you! Much obliged.
Really appreciate you sharing this blog article.Thanks Again. Awesome.
Thanks for sharing, this is a fantastic blog.Really looking forward to read more. Really Cool.
Really appreciate you sharing this article.Much thanks again. Fantastic.
I cannot thank you enough for the blog.Really thank you! Keep writing.
Great, thanks for sharing this article post.Much thanks again. Really Great.
Really informative blog article.Much thanks again. Fantastic.
Major thanks for the blog post. Fantastic.
I appreciate you sharing this article post. Keep writing.
Thank you ever so for you blog.Much thanks again. Keep writing.
I was wondering if you ever considered changing the page layout of your blog?
Its very well written; I love what youve got to say.
But maybe you could a little more in the way of content so
people could connect with it better. Youve got an awful lot of text
for only having 1 or 2 images. Maybe you could space it out
better?
Hey, thanks for the blog article. Awesome.
Really appreciate you sharing this blog. Really Great.
I appreciate you sharing this article post.Thanks Again. Want more.
I appreciate you sharing this blog article.Much thanks again. Cool.
Thanks for the blog post.Much thanks again. Will read on…
Post writing is also a excitement, if you be familiar with after that you can write if not it is
difficult to write.
Really enjoyed this article.Really looking forward to read more. Much obliged.
I really like and appreciate your article.Thanks Again. Want more.
I appreciate you sharing this blog. Keep writing.
I am so grateful for your article.Much thanks again. Much obliged.
I really liked your article. Want more.
Highly descriptive article, I loved that a lot.
Will there be a part 2?
I really liked your blog.Much thanks again. Really Cool.
I really like and appreciate your blog post.Thanks Again. Really Cool.
Hi there! I know this is kinda off topic however I’d figured I’d
ask. Would you be interested in exchanging links or maybe guest writing a blog article or vice-versa?
My blog discusses a lot of the same subjects as yours and I feel we could
greatly benefit from each other. If you might be interested feel free to shoot me an e-mail.
I look forward to hearing from you! Great blog by the way!
I really liked your blog article.Really looking forward to read more.
Muchos Gracias for your post.Thanks Again. Great.
Enjoyed every bit of your article post.Really looking forward to read more. Really Great.
Im thankful for the article.Much thanks again. Really Great.
Im thankful for the blog post. Will read on…
Thank you ever so for you article.Much thanks again.
I loved your blog.Much thanks again. Will read on…
Great blog.Much thanks again. Great.
Unquestionably imagine that that you stated.
Your favourite justification appeared to be at the internet the easiest thing to be mindful of.
I say to you, I definitely get irked whilst people consider worries that they plainly do not recognise about.
You controlled to hit the nail upon the highest and defined out the entire thing
without having side-effects , people can take a
signal. Will likely be again to get more. Thank you
Great article.Much thanks again.
wow, awesome article.Really thank you! Great.
Enjoyed every bit of your article. Want more.
I value the blog post.Much thanks again. Really Cool.
I think this is a real great post.Really thank you! Will read on…
This is one awesome post.Really looking forward to read more. Great.
Major thanks for the post.Really thank you! Really Great.
Appreciate you sharing, great blog.Thanks Again. Want more.
wow, awesome article post. Really Great.
I really enjoy the blog. Really Great.
A round of applause for your blog post.Really looking forward to read more. Much obliged.
I really liked your article.Really looking forward to read more. Keep writing.
This is a topic that is near to my heart… Many thanks!
Exactly where are your contact details though?
Im grateful for the article.Thanks Again. Great.
I every time spent my half an hour to read this website’s posts daily
along with a mug of coffee.
Im obliged for the post. Much obliged.
wow, awesome article.Thanks Again. Cool.
I am so grateful for your blog post.Really thank you! Keep writing.
Appreciate you sharing, great blog.Really thank you! Great.
This is one awesome blog article. Awesome.
Muchos Gracias for your article post.Much thanks again. Fantastic.
I really like and appreciate your article.Much thanks again. Really Great.
I really enjoy the blog.Really thank you!
Really appreciate you sharing this blog article. Awesome.
Wow, great article post.Much thanks again. Want more.
Really informative article post.Really thank you! Cool.
Major thankies for the post.Much thanks again. Will read on…
A round of applause for your blog article.Really thank you! Will read on…
Major thanks for the post.Much thanks again. Keep writing.
I am so grateful for your blog post.
A big thank you for your blog post.Really thank you!
Great, thanks for sharing this blog article.Thanks Again. Much obliged.
Very good article.Really thank you! Will read on…
I really enjoy the blog post. Awesome.
Thanks for the blog post.Thanks Again. Cool.
Thanks so much for the blog article.Really thank you! Really Cool.
Really informative blog article.Thanks Again. Really Cool.
I’ve been absent for a while, but now I remember why I used to love this website. Thank you, I will try and check back more often. How frequently you update your site?
Really informative blog.Much thanks again. Much obliged.
A round of applause for your article.Much thanks again.
Im grateful for the blog article.Really thank you! Awesome.
Enjoyed every bit of your blog article.Much thanks again. Really Great.
Thank you ever so for you blog. Great.
Awesome post.Really thank you! Want more.
I really liked your article. Really Cool.
Looking forward to reading more. Great blog post.Really looking forward to read more. Want more.
I appreciate you sharing this post.Much thanks again. Cool.
Thanks so much for the post.Really looking forward to read more. Much obliged.
Fantastic blog article.Thanks Again. Will read on…
Thanks a lot for the blog post.Really thank you! Will read on…
Say, you got a nice blog.Really thank you! Awesome.
Thank you for your post.Thanks Again. Really Great.
I loved your post. Fantastic.
A big thank you for your blog article. Fantastic.
Thanks for the blog post.Really thank you! Keep writing.
Hey, thanks for the blog. Want more.
Say, you got a nice post.Thanks Again. Really Cool.
Really informative article.Thanks Again. Awesome.
I am so grateful for your post. Really Cool.
Very neat post. Keep writing.
This is one awesome blog post.Thanks Again. Really Cool.
Thank you for your post.
Im grateful for the article. Cool.
Very informative post. Really Cool.
Great article post.Thanks Again. Keep writing.
Thanks again for the article post. Awesome.
Im thankful for the article post. Really Great.
I value the blog post.Much thanks again. Awesome.
I value the blog.Thanks Again. Want more.
Great blog post.Thanks Again. Fantastic.
Thanks for sharing, this is a fantastic blog.Thanks Again. Really Cool.
Great, thanks for sharing this blog post.Thanks Again. Really Great.
I truly appreciate this post.Really thank you! Great.
This is one awesome blog.Thanks Again. Great.
Thanks for sharing, this is a fantastic article post.Thanks Again. Want more.
wow, awesome article.Much thanks again. Keep writing.